package com.suanfa.dfs;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个n, 代表n个（）, 求所有合法的组合
 */
public class Parentheses {


    public static void main(String[] args) {
        List<String> arr = new ArrayList<>();
        int  n =3;
        new Parentheses().generate(arr, n, n, "");
        System.out.println(JSON.toJSONString(arr));

        System.out.println(JSON.toJSONString(new Parentheses().generateParenthesis(n)));
    }




        public void generate(List<String> arr, int l, int r, String stringBuilder){
            if(l == 0 && r == 0){
                arr.add(stringBuilder);
                return;
            }

            if(l>0){
                generate(arr, l-1, r, stringBuilder+"(");
            }

            if(r> l){
                generate(arr, l, r-1, stringBuilder+")");
            }

        }

    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        generateOne(res, "", n, n);
        return res;
    }

    private void generateOne(List<String> list, String string, int left, int right) {
        // left, rigth 分别代表可用的左括号数和可用的右括号数，初始都是 n个可用
        if (left == 0 && right == 0) {
            list.add(string);
            return;
        }

        if (left > 0) {
            generateOne(list, string + "(", left - 1, right);
        }

        // 可用的括号 右括号大于左括号时，说明有 左括号先放置，才会是有效的括号组合
        if (right > left) {
            generateOne(list, string + ")", left, right - 1);
        }

    }
}
